import java.util.*;

class Small implements Comparator<ListNode> {

    @Override
    public int compare(ListNode o1, ListNode o2) {
        return o1.val - o2.val;
    }
}

public class ListNodes {
    public static void main(String[] args) {
        char[] charArray = "eat".toCharArray();
        Arrays.sort(charArray);
        System.out.println(charArray);
        String s = new String(charArray);
        System.out.println(charArray);
        Map<Character, List<String>> map = new HashMap<>();
        Iterator<Character> iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            Character character = iterator.next();
        }
        PriorityQueue<ListNode> pq = new PriorityQueue<>(3, new Small());
        pq.add(new ListNode(3));
        pq.add(new ListNode(2));
        pq.add(new ListNode(1));
        System.out.println(pq);
        System.out.println(pq.poll().val);
        System.out.println(pq.poll().val);
        System.out.println(pq.poll().val);
    }

    /**
     * K 个一组翻转链表
     */
    //暴力解法 模拟
    ListNode head1 = null;
    public ListNode reverseKGroup(ListNode head, int k) {
        int n = 0;
        for(ListNode cur = head; cur != null; cur = cur.next) n++;
        int times = 0;

        ListNode newHead = new ListNode();
        newHead.next = head;
        ListNode cur = head;
        head1 = newHead;
        while(cur != null && (times + 1) * k <= n){
            cur = reverse(cur, k);
            times++;
        }
        return newHead.next;
    }

    ListNode reverse(ListNode l, int k){
        ListNode head = new ListNode();
        ListNode cur = l;
        for(int i = 0; i < k; i++){
            ListNode tmp = head.next;
            ListNode tmp1 = cur;
            cur = cur.next;
            head.next = tmp1;
            tmp1.next = tmp;
        }

        //将前后连起来
        l.next = cur;
        head1.next = head.next;
        head1 = l;

        return cur;
    }
    /**
     * 合并 K 个升序链表
     */
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if(n==0) return  null;
        // System.out.print(n);
        PriorityQueue<ListNode> pq = new PriorityQueue<>(n, new Small());
        ListNode head = new ListNode();
        for(int i = 0; i < n; i++){
            if(lists[i] == null) continue;
            pq.add(lists[i]);
        }
        ListNode cur = head;
        ListNode tmp = new ListNode();
        while(!pq.isEmpty()){
            tmp = pq.poll();
            cur.next = tmp;
            cur = tmp;
            tmp = tmp.next;
            if(tmp != null){
                pq.add(tmp);
            }
        }
        cur.next = null;
        return head.next;
    }
    public ListNode mergeKListsRecursion(ListNode[] lists) {
        int n = lists.length;
        if(n == 0) return null;
        return recursionLists(lists,0,n-1);
    }

    ListNode recursionLists(ListNode[] lists, int left, int right){
        if(left>=right){
            return lists[left];
        }

        int mid = (left+right)/2;

        ListNode r = recursionLists(lists, left, mid);
        ListNode l = recursionLists(lists, mid + 1, right);

        //合并r l
        ListNode head = new ListNode();
        ListNode cur = head;
        ListNode i = l;
        ListNode j = r;
        for(; i != null && j != null; ){
            if(i.val < j.val){
                cur.next = i;
                i = i.next;
            }else{
                cur.next = j;
                j = j.next;
            }
            cur = cur.next == null ? cur : cur.next;
        }

        if(i != null) cur.next = i;
        if(j != null) cur.next = j;

        return head.next;
    }
    /**
     * 重排链表
     */
    public void reorderList(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        for(; fast != null; ){
            if(fast.next == null || fast.next.next == null) break;
            slow = slow.next;
            fast = fast.next.next;
        }

        if(slow == head) return;

        //翻转slow。next
        ListNode l = slow.next;
        ListNode r = l.next;
        ListNode p = r == null ? null : r.next;
        l.next = slow;
        for(;r != null;){
            r.next = l;
            l = r;
            r = p;
            if(p == null) break;
            p = p.next;
        }

        //拼接
        ListNode cur = head;
        for(; cur != slow;){
            ListNode tmpC = cur.next;
            ListNode tmpL = l.next;

            cur.next = l;
            l.next = tmpC;

            cur = tmpC;
            l = tmpL;
        }
        if(l != slow) {
            cur.next = l;
            cur = cur.next;
        }
        cur.next = null;
    }

    /**
     * 两数相加 II
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);

        //相加
        ListNode ret = new ListNode();
        ListNode i = l1;
        ListNode j = l2;
        int carry = 0;
        for (; i != null && j != null; i = i.next, j = j.next) {
            int v = i.val + j.val + carry;
            carry = v / 10;
            v %= 10;
            ListNode node = new ListNode(v);
            headAdd(ret, node);
        }

        while (i != null) {
            int v = i.val + carry;
            carry = v / 10;
            v %= 10;
            ListNode node = new ListNode(v);
            headAdd(ret, node);
            i = i.next;
        }

        while (j != null) {
            int v = j.val + carry;
            carry = v / 10;
            v %= 10;
            ListNode node = new ListNode(v);
            headAdd(ret, node);
            j = j.next;
        }

        if (carry != 0) headAdd(ret, new ListNode(1));

        return ret.next;
    }

    ListNode reverse(ListNode l) {
        ListNode head = new ListNode();
        int size = 0;
        //头插
        for (ListNode i = l; i != null; i = i.next) {
            headAdd(head, new ListNode(i.val));
            size++;
        }
        head.val = size;
        return head.next;
    }

    void headAdd(ListNode head, ListNode add) {
        ListNode tmp = head.next;
        head.next = add;
        head.next.next = tmp;
    }
}
